package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/29 18:40
 * @Description:将BST转化为累加树,还是借助BST中序遍历的特点
 * 累加树要将每个节点值更新为大于等于当前节点值
 * 所以可以先遍历右子树，从右子树最右侧节点开始累加，依次遍历每个节点更新值即可
 */
public class Num538_ConvertTree {
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }
    int sum = 0;
    private void traverse(TreeNode root) {
        // base case
        if (root == null) {
            return;
        }
        traverse(root.right);
        sum += root.val;
        // 更新当前节点值
        root.val = sum;
        traverse(root.left);
    }
}
